#!/usr/bin/python

import os

######################################################################
# Question 1: See the demo*.jpg files in this directory
######################################################################


######################################################################
# Question 2: The interface for the dot module:
######################################################################
def newDot():
    return 'digraph g {\n\tordering = out\n'
# dot dotInsert(), not void dotInsert();    A little ugly here :-)
def dotInsert(d, fr, to, info = None):
    d = d + '\t' + '"' + fr + '"'+ ' -> ' + '"' + to + '"'
    if info != None:
        d = d + ' [label="%s"];\n' % info
    else:
        d = d + ';\n'
    return d
def dotToJpg(d, fileName):
    d = d + '}\n'                 # Don't forget d need a '}' to terminate!
    f = open(fileName + '.dot', 'w')
    f.write(d)
    f.close()
    cmd = 'dot -Tjpg %s.dot -o %s.jpg' % (fileName, fileName)
    os.system(cmd)


######################################################################
# Question 3: Extensible "tree" ADT
######################################################################
def visit(x):
    print 'Now visiting ' + x

class newTree:
    def __init__(self):
        self.vertex = {}
    def treeInsertVertex(self, v):
        self.vertex[v] = {}
    def treeInsertEdge(self, fr, to):
        self.vertex[fr][to] = None
    def treeInsertEdgeInfo(self, fr, to, info):
        self.vertex[fr][to] = info
    def treeToJpg(self, fileName):
        self.d = newDot()
        for x in sorted(self.vertex):
            for y in sorted(self.vertex[x]):
                self.d = dotInsert(self.d, x, y, self.vertex[x][y])
        dotToJpg(self.d, fileName)
    def treePreOrder(self, root, visit):
        visit(root)
        for x in sorted(self.vertex[root]):
            self.treePreOrder(x, visit)
    def treeInOrder(self, root, visit):
        if len(self.vertex[root]) == 0:
            visit(root)
        else:
            self.treeInOrder(sorted(self.vertex[root])[0], visit)
            visit(root)
            for x in sorted(self.vertex[root])[1:]:
                self.treeInOrder(x, visit)
    def treePostOrder(self, root, visit):
        for x in sorted(self.vertex[root]):
            self.treePostOrder(x, visit)
        visit(root)
    def treeLevelOrder(self, root, visit):
        queue = [root]
        while len(queue) > 0:
            n = queue.pop(0)
            visit(n)
            for x in sorted(self.vertex[n]):
                queue.append(x)


######################################################################
# Question 4: Extensible "graph" ADT
######################################################################
class newGraph:
    def __init__(self):
        self.vertex = {}
    def graphInsertVertex(self, v):
        self.vertex[v] = {}
    def graphInsertEdge(self, fr, to):
        self.vertex[fr][to] = None
    def graphInsertEdgeInfo(self, fr, to, info):
        self.vertex[fr][to] = info
    def graphToJpg(self, fileName):
        self.d = newDot()
        for x in self.vertex:
            for y in self.vertex[x]:
                self.d = dotInsert(self.d, x, y, self.vertex[x][y])
        dotToJpg(self.d, fileName)
    def dfs(self, start, visit):
        visit(start)
        self.visited.append(start)
        for x in sorted(self.vertex[start]):
            if x not in self.visited:
                self.dfs(x, visit)
    def graphDfs(self, start, visit):
        self.visited = []
        self.dfs(start, visit)
        for x in sorted(self.vertex):
            if x not in self.visited:
                self.dfs(x, visit)
    def bfs(self, start, visit):
        queue = [start]
        while len(queue) > 0:
            n = queue.pop(0)
            if n not in self.visited:
                visit(n)
                self.visited.append(n)
            for x in sorted(self.vertex[n]):
                if x not in self.visited:
                    queue.append(x)
    def graphBfs(self, start, visit):
        self.visited = []
        self.bfs(start, visit)
        for x in sorted(self.vertex):
            if x not in self.visited:
                self.bfs(x, visit)


######################################################################
# Let's take two examples:
######################################################################
tn = 'sample_tree'
t = newTree()
t.treeInsertVertex('1')
t.treeInsertVertex('2')
t.treeInsertVertex('3')
t.treeInsertEdgeInfo('1', '2', 'son')
t.treeInsertEdgeInfo('1', '3', 'daughter')
print 'Generating %s.dot and %s.jpg...' % (tn, tn),
t.treeToJpg(tn)
print 'Done.'
print 'Visit the tree in %s.jpg in PreOrder:' % tn
t.treePreOrder('1', visit)
print 'Visit the tree in %s.jpg in InOrder:' % tn
t.treeInOrder('1', visit)
print 'Visit the tree in %s.jpg in PostOrder:' % tn
t.treePostOrder('1', visit)
print 'Visit the tree in %s.jpg in LevelOrder:' % tn
t.treeLevelOrder('1', visit)

print '----------------------------------------------------------------------'

gn = 'sample_graph'
g = newGraph()
g.graphInsertVertex('1')
g.graphInsertVertex('2')
g.graphInsertVertex('3')
g.graphInsertVertex('4')
g.graphInsertVertex('5')
g.graphInsertVertex('6')
g.graphInsertEdge('1', '2')
g.graphInsertEdge('1', '4')
g.graphInsertEdge('2', '5')
g.graphInsertEdge('5', '4')
g.graphInsertEdge('4', '2')
g.graphInsertEdge('3', '5')
g.graphInsertEdge('3', '6')
g.graphInsertEdge('6', '6')
print 'Generating %s.dot and %s.jpg...' % (gn, gn),
g.graphToJpg(gn)
print 'Done.'
print 'Visit the tree in %s.jpg in Dfs:' % gn
g.graphDfs('1', visit)
print 'Visit the tree in %s.jpg in Bfs:' % gn
g.graphBfs('1', visit)

raw_input('\nPress enter to exit')
